package interview.huawei.tjt.training.huisu;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 * 说明：
 *
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
 *
 * 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
 */
public class ZuHeZongHe {

    private static List<List<Integer>> result = new ArrayList<>();
    private static LinkedList<Integer> path = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int k = sc.nextInt();
            int n = sc.nextInt();
            helper(n, k, 1);
            System.out.println(result);
            result.clear();
        }

    }

    public static void helper (int n, int k, int startIndex) {
        // 终止条件
        if (path.size() == k) {
            int sum = 0;
            for (int i = 0; i < k; i ++) {
                sum += path.get(i);
            }
            if (sum == n) {
                result.add(new ArrayList<>(path));
            }
            return;
        }

//        for (int i = startIndex; i <= n; i ++) {  // 未做剪枝处理
        for (int i = startIndex; i <= n - 3 - (k - path.size()) + 1; i ++) {  // 做了剪枝处理
            path.add(i);
            helper(n, k,i + 1);
            // 回溯
            path.removeLast();
        }
    }

}
